package problem188_Best_Time_to_Buy_and_Sell_Stock_IV;

/**
 * global[i][j]代表前i天最多j次交易获得的最大利润，local[i][j]代表前i天最多进行j次交易且最后一次交易发生在第i天获得的最大利润。
 * global[i][j]=max(global[i-1][j],local[i][j]);
 * local[i][j]=max(global[i-1][j-1]+max(0,diff),local[i-1][j]+diff); diff=price[i]-price[i-1]
 * local[i][j]可以这样考虑，最后一笔交易卖出发生在第i天，有两种情况：
 * （1）最后一笔交易买入在i-1天之后，那么local = global[i-1][j-1]+max(0,diff)；
 * （2）最后一笔交易买入在i-1天之前，那么local=local[i-1][j]+diff;
 * 
 * http://www.cnblogs.com/grandyang/p/4295761.html
 * http://liangjiabin.com/blog/2015/04/leetcode-best-time-to-buy-and-sell-stock.html
 * 
 * @author I321035
 *
 */

public class Solution {
	public int maxProfit(int k, int[] prices) {
		int days=prices.length;
		if(k>=days)
			return maxProfit2(prices);
		int[][] global=new int[days][k+1];
		int[][] local=new int[days][k+1];
		for(int i=1;i<days;i++){
			int diff=prices[i]-prices[i-1];
			for(int j=1;j<=k;j++){
				local[i][j]=Math.max(global[i-1][j-1]+Math.max(0, diff), local[i-1][j]+diff);
				global[i][j]=Math.max(global[i-1][j], local[i][j]);
			}
		}
		return global[days-1][k];
    }
	
	public int maxProfit2(int[] prices) {
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                maxProfit += prices[i] - prices[i - 1];
            }
        }
        return maxProfit;
    }
}
